'''
https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/description/
'''
from typing import Optional


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        help = []
        while head:
            help.append(head.val)
            head = head.next

        def build(l, r):
            if l > r: return None
            mid = l + r >> 1
            root = TreeNode(help[mid])
            root.left = build(l, mid - 1)
            root.right = build(mid + 1, r)
            return root
        return build(0, len(help) - 1)

    def sortedListToBST2(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        def find_mid(head):
            prev = None
            slow, fast = head, head
            while fast.next and fast.next.next:
                fast = fast.next.next
                prev = slow
                slow = slow.next
            return prev, slow

        def build(head):
            if not head: return None
            prev, mid = find_mid(head)
            next = mid.next
            mid.next = None
            if prev:
                prev.next = None
            root = TreeNode(mid.val)
            if prev:
                root.left = build(head)
            root.right = build(next)
            return root
        return build(head)
